package leetcode_1701_1800;

import java.util.HashSet;
import java.util.Set;

public class LeeCode_1733_slow {
    public static void main(String[] args) {

//        System.out.println(minimumTeachings(2, new int[][]{{1}, {2}, {1, 2}}, new int[][]{{1, 2}, {1, 3}, {2, 3}}));
//        System.out.println(minimumTeachings(3, new int[][]{{2}, {1,3}, {1, 2},{3}}, new int[][]{{1, 4}, {1, 2}, {3, 4},{2,3}}));
        System.out.println(minimumTeachings(3, new int[][]{{2}, {1,3}, {1, 2},{3}}, new int[][]{{3,4}}));
    }
    private static int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        int m = languages.length;
        Set<Integer>[] sets = new HashSet[m + 1];
        for (int i = 0; i <= m; i++) {
            sets[i] = new HashSet<>();
        }
        for (int i = 0; i < m; i++) {
            for (int j : languages[i]) {
                sets[i + 1].add(j);
            }
        }
        int ans = m;
        for (int i = 1; i <= n; i++) {
            Set<Integer> count = new HashSet<>();
            for (int j = 0; j < friendships.length; j++) {
                boolean flag = false;
                int x = friendships[j][0], y = friendships[j][1];
                for (Integer l1 : sets[x]) {
                    if (sets[y].contains(l1)){
                        flag = true;
                        break;
                    }
                }
                if (!flag){
                    if (!sets[x].contains(i)){
                        count.add(x);
                    }
                    if (!sets[y].contains(i)){
                        count.add(y);
                    }
                }
            }
            ans = Math.min(ans, count.size());
        }
        return ans;
    }
}
